package sublinear.algorithm;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.Stack;
import java.util.logging.Logger;

import sublinear.common.SimplePRNG;
import sublinear.model.AbstractGraph;
import sublinear.model.AbstractGraph.GraphNode;
import sublinear.model.db.AdjacencyList;
//import sublinear.model.NodeColor; //obsolete
import sublinear.model.db.DbGraph;

public class GraphSearch {
	
	private static final Logger log = Logger.getLogger( DbGraph.class.getName() );
	
	private static final int unvisited = -1;

	public static long breadthFirstSearch(AbstractGraph G, GraphNode s, long maxNodes, ArrayDeque<GraphNode> Q, Map<Long,GraphNode> visitedIds)
	{
		int numEdges = s.getNumEdges(); //resume BFS from were it stopped
		long visitedNodes = 0;
		if (!visitedIds.containsKey(s.getUniqueId())){
			visitedIds.put(s.getUniqueId(),s);
			Q.addFirst(s);
		}
		while (!Q.isEmpty()){
			GraphNode u = Q.removeLast();
			if (maxNodes <= ++visitedNodes){
				visitedNodes--;
				Q.addFirst(u);
				break;
			}
			for (GraphNode v : G.getNeighbors(u)){
				if (!visitedIds.containsKey(v.getUniqueId())){
					visitedIds.put(v.getUniqueId(),v);
					Q.addFirst(v);
				}
				numEdges++;
			}
		}
		s.setNumEdges(numEdges);
		return visitedNodes;
	}
	
	public static HashSet<Long> bfs(AbstractGraph G, GraphNode s, Set<Long> visitedIds){
		
		HashSet<Long> wcc = new HashSet<Long>();
		ArrayDeque<GraphNode> Q = new ArrayDeque<GraphNode>();
		
		visitedIds.add(s.getUniqueId());
		wcc.add(s.getUniqueId());
		Q.addFirst(s);
		
		while (!Q.isEmpty()){
			GraphNode u = Q.removeLast();

			for (GraphNode v : G.getNeighbors(u)){
				if (!visitedIds.contains(v.getUniqueId())){
					visitedIds.add(v.getUniqueId());
					wcc.add(v.getUniqueId());
					Q.addFirst(v);
				}
			}
		}
		return wcc;
		
	}
	
	public static HashSet<HashSet<Long>> weaklyConnect(AdjacencyList G) {  
	
		HashSet<Long> visitedIds = new HashSet<Long>();
		HashSet<HashSet<Long>> weakCCs = new HashSet<HashSet<Long>>();


		for (Long id : G.getNodeIds()){
			if (!visitedIds.contains(id)){
				
				HashSet<Long> wcc = bfs(G,G.getGraphNode(id),visitedIds);
				weakCCs.add(wcc);
				
				if(weakCCs.size()%1000==0 || wcc.size()>1) 
					log.info("Discovered SCC of size: "+wcc.size()+" Total SCCs count: "+weakCCs.size());
				weakCCs.add(wcc);
			}
		}	
		return weakCCs;
    }
	

	
	public static void randomGraphWalk(AbstractGraph G, long maxNodes)
	{
		GraphNode node = null;
		node = G.getRandomNode();
		
		for (int i = 0; i < maxNodes; ++i) {
			log.info("Visit: " + node.getFriendlyName());
			ArrayList<GraphNode> neighbors = G.getNeighbors(node);
			if (neighbors.size() == 0) {
				// Should not happen after the first node, as we got at
				// least the one we came from... could indicate a bug
				log.info("No neighbors - jump to a random location");
				node = G.getRandomNode();
			} else {
				node = neighbors.get(SimplePRNG.getInstance().nextInt(neighbors.size()));
			}
		}
	}
	
	public static class TarjanStack<T>{
		
		Set<T> S;
		Stack<T> stck;
		
		TarjanStack(){
			S = new HashSet<T>();
			stck = new Stack<T>();
		}
		
		
		public void push(T item){
			stck.push(item);
			S.add(item);
		}
		
		public T pop(){
			T item = stck.pop();
			S.remove(item);
			return item;
		}
		
		public boolean contains(T item){
			return S.contains(item);
		}
	}
	
	
	public static HashSet<HashSet<GraphNode>> tarjanRecursive(AdjacencyList G){
		
		TarjanStack<GraphNode> visitedStack = new TarjanStack<GraphNode>(); //stack
		HashSet<HashSet<GraphNode>> strongCCs = new HashSet<HashSet<GraphNode>>();
		
		for (Long id : G.getNodeIds()){
			GraphNode v = G.getGraphNode(id);
			if (v.index == unvisited){
				strongConnect(G, v,visitedStack, 0, strongCCs);
			}
		}	
		return strongCCs;
		
	}
	
	
	private static void strongConnect(AdjacencyList G, GraphNode v, 
			TarjanStack<GraphNode> S, int index, HashSet<HashSet<GraphNode>> SCCs){
		
		v.setIndex(index);
		v.setLowlink(index);
		index++;
		 S.push(v);
		
		// iterate over successors of v
		for (GraphNode w : G.getNeighbors(v)){
			if (w.getIndex() == unvisited){
				// successor w has not yet been visited; recurse on it
				strongConnect(G, w, S, index, SCCs);
				
				v.setLowlink(Math.min(v.getLowlink(), w.getLowlink()));
			} else if(S.contains(w)){
				v.setLowlink(Math.min(v.getLowlink(), w.getIndex()));
			}
		}
		
	    //v is a root node, pop the stack and generate an SCC
		if (v.getLowlink() == v.getIndex()){
			
			GraphNode u;
			HashSet<GraphNode> scc = new HashSet<GraphNode>();
			do {
				u = S.pop();
				scc.add(u);
			} while ((u != v));
			
			SCCs.add(scc);
			
		}
			
	}
	
	private static void outputCC(GraphNode last, TarjanStack<GraphNode> stck, HashSet<HashSet<GraphNode>> SCCs){
		
		HashSet<GraphNode> scc = new HashSet<GraphNode>();
        GraphNode top = stck.pop();
        scc.add(top);

        while(top.getUniqueId() != last.getUniqueId()) {
            top = stck.pop();
            scc.add(top);
        }
		if(SCCs.size()%1000==0 || scc.size()>1) 
			log.info("Discovered SCC of size: "+scc.size()+" Total SCCs count: "+SCCs.size());
		SCCs.add(scc);
	}


	public static HashSet<HashSet<GraphNode>> tarjanIterative(AdjacencyList G) {  
		
		TarjanStack<GraphNode> tarjanStack = new TarjanStack<GraphNode>(); //stack
		HashSet<HashSet<GraphNode>> strongCCs = new HashSet<HashSet<GraphNode>>();
		
		for (Long id : G.getNodeIds()){
			GraphNode v = G.getGraphNode(id);
			if (v.index == unvisited){
				tarjanIterativeHelper(G, v, 0, tarjanStack, strongCCs);
			}
		}	
		return strongCCs;
    }


	static void tarjanIterativeHelper(AdjacencyList G, GraphNode u, int index, TarjanStack<GraphNode> stck, HashSet<HashSet<GraphNode>> SCCs) {
	    u.index = index;
	    u.lowlink = index;
	    index++;
	    u.vindex = 0; 			// index from which neighbor to continue the recursion
	    stck.push(u);
	    u.caller = null;           //Equivalent to the node from which the recursive call would spawn.
	    GraphNode last = u;
	    while(true) {
	    	ArrayList<GraphNode> nList = G.getNeighbors(last);
	        if(last.vindex < nList.size()) {       //Equivalent to the check in the for-loop in the recursive version
	            GraphNode w = nList.get(last.vindex);
	            last.vindex++;                                   //Equivalent to incrementing the iterator in the for-loop in the recursive version
	            if(w.index == unvisited) { // successor w has not yet been visited; recurse on it
	                w.caller = last;                     
	                w.vindex = 0;
	                w.index = index;
	                w.lowlink = index;
	                index++;
	                stck.push(w);
	                last = w;
	            } else if(stck.contains(w)) {
	                last.lowlink = Math.min(last.lowlink, w.index);
	            }
	        } else {  //Equivalent to the nodeSet iterator pointing to end()
	            if(last.lowlink == last.index) {
	            	
	            	outputCC(last, stck, SCCs);
	            }
	
	            GraphNode newLast = last.caller;   //Go up one recursive call
	            if(newLast != null) {
	                newLast.lowlink = Math.min(newLast.lowlink, last.lowlink);
	                last = newLast;
	            } else {   //We've seen all the nodes
	                break;
	            }
	        }
	    }
	}

}
